\section{等待队列设计与实现}\label{ux7b49ux5f85ux961fux5217ux8bbeux8ba1ux4e0eux5b9eux73b0}

为了支持用户进程完成特定事件的等待和唤醒操作，ucore设计了等待队列，从而使得用户进程可以方便地实现由于某事件没有完成而睡眠，并且在事件完成后被唤醒的整个操作过程。

其基本设计思想是：当一个进程由于某个事件没有产生而需要在某个睡眠等待时，设置自身运行状态为PROC\_SLEEPING，等待原因为某事件，然后将自己的进程控制块指针和等待标记组装到一个数据结构为wait\_t的等待项数据中，并把这个等待项的挂载到等待队列wait\_queue的链表中，再执行schedule函数完成调度切换；当某些事件发生后，另一个任务（进程）会唤醒等待队列wait\_queue上的某个或者所有进程，唤醒操作就是将等待队列wait\_queue中的等待项中的进程运行状态设置为可调度的状态，并且把等待项从等待队列中删除。下面是等待队列的设计与实现分析。

\subsection{数据结构描述}\label{ux6570ux636eux7ed3ux6784ux63cfux8ff0}

等待项的定义：

\begin{lstlisting}
typedef struct {
    struct proc_struct *proc;
    uint32_t wakeup_flags;
    wait_queue_t *wait_queue;
    list_entry_t wait_link;
} wait_t;
\end{lstlisting}

这里等待项的成员变量proc表明了等待某事件的进程控制块指针，wakeup\_flags是唤醒进程的事件标志（多个标志可以有逻辑或的关系，形成复合事件标志），wait\_queue是此等待项所属的等待队列，wait\_link用于链接到等待队列wait\_queue中。

等待队列的定义：

\begin{lstlisting}
typedef struct {
    list_entry_t wait_head;
} wait_queue_t;
\end{lstlisting}

等待队列就是一个双向链表的头指针。

\subsection{等待队列相关操作函数}\label{ux7b49ux5f85ux961fux5217ux76f8ux5173ux64cdux4f5cux51fdux6570}

\subsubsection{初始化}\label{ux521dux59cbux5316}

如果要使用等待队列，首先需要声明并初始化等待队列。以proj11为例，在kern/mm/swap.c中有一个等待队列的变量声明和在swap\_init函数中执行的对应初始化：

\begin{lstlisting}
static wait_queue_t kswapd_done;
…
wait_queue_init(&kswapd_done);
\end{lstlisting}

\subsubsection{执行等待}\label{ux6267ux884cux7b49ux5f85}

如果某进程需要等待某事件，则需要设置自己的运行状态为PROC\_SLEEPING，构建并初始化一个等待项，再挂入到某个等待队列中。以proj11为例，某进程申请内存资源无法满足，需要等待kswapd内核线程给系统更多的内核资源，于是在try\_free\_pages函数中执行了如下操作：

\begin{lstlisting}
wait_t __wait, *wait = &__wait;
wait_init(wait, current);
       current->state = PROC_SLEEPING;
       current->wait_state = WT_KSWAPD;
       wait_queue_add(&kswapd_done, wait);
\end{lstlisting}

这里可以看到，首先声明了一个等待项\_\_wait，然后调用wait\_init函数对此等待项进行了初始化；并进一步把当前进程的运行状态设置为PROC\_SLEEPING，睡眠原因设置为WT\_KSWAPD，即等待kswapd释放出更多的空闲内存；最后把此等待项加入到等待队列kwapd\_done中。

\subsubsection{执行唤醒}\label{ux6267ux884cux5524ux9192}

当某个事件产生后，需要唤醒等待在等待队列中的睡眠进程。以proj11为例，当kswapd内核线程释放出更多的空闲内存后，就需要唤醒等待更多内存的进程，在kswapd内核线程的主体执行函数kswapd\_main中调用了

\begin{lstlisting}
kswapd_wakup_all函数：
wakeup_queue(&kswapd_done, WT_KSWAPD, 1);
\end{lstlisting}

这个函数就完成了唤醒功能，它会遍历kswapd\_done等待队列上的所有等待项，找到一个就执行wakeup\_wait函数，来进一步调用wakup\_proc函数来唤醒挂在等待项上的睡眠进程。

上面是使用等待队列的基本流程。为了能够更好地完善整个基于等待队列的等待唤醒机制，在wait.{[}ch{]}中提供了一系列函数：

\begin{itemize}
\item
  void wait\_init：初始化等待项
\item
  void wait\_queue\_init：初始化等待队列
\item
  void wait\_queue\_add：把一个等待项加入到一个等待队列中
\item
  void wait\_queue\_del：从一个等待队列中删除一个等待项
\item
  wait\_t
  *wait\_queue\_next：查找挂在某等待队列中的等待项指向的下一个等待项
\item
  wait\_t
  *wait\_queue\_prev：查找挂在某等待队列中的等待项指向的前一个等待项
\item
  wait\_t *wait\_queue\_first：查找挂在某等待队列中的第一个等待项
\item
  wait\_t *wait\_queue\_last：查找挂在某等待队列中的最后一个等待项
\item
  bool wait\_queue\_empty：判断等待队列是否为空
\item
  bool wait\_in\_queue：单品某等待项是否在等待队列中
\item
  void
  wakeup\_wait：唤醒等待项中的睡眠进程，删除等待队列中的等待项（参数del确定是否删除）
\item
  void
  wakeup\_first：唤醒等待队列中第一个等待项中的睡眠进程，删除等待队列中的这个等待项（参数del确定是否删除）
\item
  void
  wakeup\_queue：唤醒等待队列中所有等待项中的睡眠进程，删除等待队列中的对应等待项（参数del确定是否删除）
\end{itemize}
